\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm,epsfig}
%\usepackage[left=1in,top=1in,right=1in,bottom=1in,nohead]{geometry}
\usepackage{fullpage}
\usepackage{subfigure}
\usepackage{color}
\usepackage{times}
\usepackage{url}
\usepackage{graphicx} 
\usepackage{ifthen} 
\setlength{\textheight}{9.12in}
\setlength{\textwidth}{6.55in}
\newboolean{short} 
%\setboolean{short}{false} 
\setboolean{short}{false} 
\newcommand{\shortOnly}[1]{\ifthenelse{\boolean{short}}{#1}{}}
\newcommand{\onlyShort}[1]{\ifthenelse{\boolean{short}}{#1}{}}
\newcommand{\longOnly}[1]{\ifthenelse{\boolean{short}}{}{#1}}
\newcommand{\onlyLong}[1]{\ifthenelse{\boolean{short}}{}{#1}}
\newcommand{\stirlingtwo}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}
\newcommand{\Gtensor}[0]{G \times G} 
\newcommand{\D}[0]{\mathcal{D}} 
\newcommand{\eul}[0]{\text{exp}} 


\def\ShowComment{True}


\ifdefined\ShowComment

\def\scott#1{\marginpar{$\leftarrow$\fbox{D}}\footnote{$\Rightarrow$~{\sf #1 \red{--Scott}}}}
\def\gopal#1{\footnote{$\Rightarrow$~{\sf #1 \red{--Gopal}}}}
\def\raj#1{\marginpar{$\leftarrow$\fbox{G}}\footnote{$\Rightarrow$~{\sf #1 \red{--Rajmohan}}}}



\else

\def\scott#1{}
\def\gopal#1{}
\def\raj#1{}

\fi


\begin{document}

\input{macros}

\begin{titlepage}

\title{Coalescing-Branching Random Walks on Graphs}


\author{Chinmoy Dutta \thanks{Twitter, San Francisco, CA.  E-mail:
    {\tt{chinmoy@twitter.com}}.  Supported in part by NSF grant
    CNS-0915985.}  \and Gopal Pandurangan \thanks{Department of
    Computer Science, University of Houston, Houston, TX 77204,
    USA. Work done while the author was affiliated with the Division
    of Mathematical Sciences, Nanyang Technological University,
    Singapore 637371 and Department of Computer Science, Brown
    University, Providence, RI 02912, USA.  \hbox{E-mail}:~{\tt
      gopalpandurangan@gmail.com}. Supported in part by the following
    grants: Nanyang Technological University grant M58110000,
    Singapore Ministry of Education (MOE) Academic Research Fund
    (AcRF) Tier 2 grant MOE2010-T2-2-082, and the US-Israel Binational
    Science Foundation grant 2008348.  }  \and Rajmohan Rajaraman
  \thanks{College of Computer and Information Science, Northeastern
    University, Boston MA 02115, USA.  E-mail: {\tt
      \{rraj,str\}@ccs.neu.edu}.  Supported in part by NSF grants
    CNS-0915985, CCF-1216038, and CCF-1422715.} \and Scott
  Roche~$^\ddagger$}

\date{}
 
\maketitle

\thispagestyle{empty}

\begin{abstract}
We study a distributed randomized information propagation mechanism
 in networks we call the {\em coalescing-branching} random walk (cobra walk, for short). A cobra walk is a generalization of the well-studied
 ``standard" random walk, and is useful in modeling and understanding the Susceptible-Infected-Susceptible (SIS)-type of epidemic processes in networks.  It can also be
 helpful in performing light-weight information dissemination in
 resource-constrained networks.  A cobra walk is parameterized by a
 {\em branching factor} $k$.  The process starts from an arbitrary
 vertex, which is labeled {\em active} for step $1$.  In
 each step of a cobra walk, each active vertex chooses $k$ random
 neighbors to become active for the next step (``branching").  A vertex
 is active for step $t+1$ only if it is chosen by an active vertex in
 step $t$ (``coalescing"). This results in a stochastic process in the
 underlying network with properties that are quite different from both the
 standard random walk (which is equivalent to the cobra walk with branching
 factor $1$) as well as other gossip-based rumor spreading mechanisms.

 We focus on the {\em cover time}\/ of the cobra walk, which is the
 number of steps for the walk to reach all the vertices, and derive
 almost-tight bounds for various graph classes.  We show an $O(\log^2 n)$ high probability bound for the cover time
 of cobra walks on expanders, if either the expansion factor or the
 branching factor is sufficiently large; we also obtain an $O(\log n)$
 high probability bound for the {\em partial cover time}, which is the
 number of steps needed for the walk to reach at least a constant
 fraction of the vertices.  We also show that the cover time of the cobra walk is, with high probability, $O(n \log
 n)$  on any $n$-vertex tree for $k \ge 2$,  $\tilde{O}(n^{1/d})$
  on a $d$-dimensional grid for $k \geq 2$, and $O(\log n)$ on the complete graph.
 \end{abstract}
{\bf Keywords:} Random Walks, Networks,
Information Spreading, Cover Time, Epidemic Processes.

\smallskip

  
\end{titlepage}

\maketitle

\section{Introduction}
We study a distributed propagation mechanism in networks, called the
{\em coalescing-branching random walk} ({\em cobra walk}, for short).
A cobra walk is a variant of the standard random walk, and is
parameterized by a {\em branching factor}, $k$.  The process starts
from an arbitrary vertex, which is initially labeled {\em active}.  For
instance, this could be a vertex that has a piece of data, rumor, or a
virus. In a cobra walk, for each discrete time step, each active vertex chooses $k$
random neighbors (sampled independently with replacement) to become
active for the next step; this is the ``branching" property, in which
each vertex spawns multiple independent random walks.  A vertex is active
for step $t$ if and only if it is chosen by an active vertex in step
$t-1$; this is the ``coalescing" property, i.e., if multiple walks
meet at a vertex, they coalesce into one walk.

A cobra walk generalizes the standard random
walk~\cite{lovasz-survey,upfal}, which is equivalent to a cobra walk
with $k = 1$.  Random walks on graphs have a wide variety of
applications, including serving as fundamental primitives in distributed
network algorithms for load balancing, routing, information
propagation, gossip, and
search~\cite{DNP09-podc,DNPT10-podc,BBSB04,ZS06}.  Being local and
requiring little state information, random walks and their variants
are especially well-suited for self-organizing dynamic networks such
as Internet overlay, ad hoc wireless, and sensor networks~\cite{ZS06}.
As a propagation mechanism, one parameter of interest is the {\em
cover time}, the expected time it takes to cover all the vertices in a
network.  Since the cover time of the standard random walk can be
large --- $\Theta(n^3)$ in the worst case, $\Theta(n \log n)$ even for
expanders \cite{lovasz-survey} --- some recent studies have studied
simple adaptations of random walks that can speed up cover
time~\cite{AHKV03,berenbrink,DP05}.  Our analysis of cobra walks
continues this line of research, with the aim of studying a
lightweight information dissemination process that has the potential
to improve cover time significantly.

Our primary motivation for studying cobra walks is their close
connection to SIS-type epidemic processes in networks.  The SIS
(standing for Susceptible Infected Susceptible)   model
(e.g., \cite{durrett2010some},  also see Section \ref{sec:apps})  is widely used for capturing the spread
of diseases in human contact networks or propagation of viruses in
computer networks.  Three basic properties of an SIS process are: (a)
a vertex can infect one or more of its neighbors (the ``branching"
property); (b) a vertex can be infected by one or more of its neighbors
(the ``coalescence" property) and (c) an infected vertex can be cured and
then become susceptible to infection at a later stage.  Cobra walks
satisfy all these properties, while standard random walks and other
gossip-based propagation mechanisms violate one or more.  Also, while
there has been considerable work on the SIS model
(\cite{GANESH,PIET, givan2011predicting,
durrett2010some, parshani2010epidemic, draief2011random,
berger2005spread}), it has been analytically hard to tackle basic {\em
coverage} questions: (1) How long will it take for the epidemic to
infect, say, a constant fraction of network? (2) Will every vertex be
infected at some point, and how long will this take?  Our analysis of
cobra walks in certain special graph classes is a step toward a better
understanding of such questions for SIS-type processes.

\subsection{Our results and techniques}

\label{sec:results}
We derive near-tight bounds on the cover time of cobra walks on trees,
grids, and expanders.  These special graph classes arise in many
distributed network applications, especially in the modeling and
construction of peer-to-peer (P2P), overlay, ad hoc, and sensor
networks.  For example, expanders have been used for modeling and
construction of P2P and overlay networks, grids and related graphs
have been used as models for ad hoc and sensor networks, and spanning
trees are often used as backbones for various information propagation
tasks.

We begin with an observation that Matthew's Theorem \cite{matthews1988covering, lovasz-survey} for random walks
extends to cobra walks; that is, the cover time of a cobra walk on an
$n$-vertex graph is at most $O(\log n)$ times the maximum hitting time of a
vertex. Hitting time is the expected time until a walk originating at $u \in V$ reaches $v \in V$ for the first time. For many graphs, the expected cover time of a random walk coincides with the high probability cover time. This enables us to
focus on deriving bounds for the hitting time.

We face two technical challenges in our analysis.  First, unlike in a
standard random walk, cobra walks have multiple ``active'' vertices at
any step, and in almost all graphs, it is difficult to characterize
the distribution of the active vertices at any point of time.  Second,
the combination of the branching and coalescing properties introduces
a non-trivial dependence among the active vertices, making it challenging
to quantify the probability that a given vertex is made active during a
given time period.  Surprisingly, these challenges manifest even in
tree networks.  We present a result that gives a tight bound on the cover time
for trees, which we obtain by establishing a recurrence relation for
the expected time taken for the cobra walk to cross an edge along a
given path of the tree.
\begin{itemize}
\item For an arbitrary $n$-vertex tree, a cobra walk with $k \ge 2$
  covers all vertices in $O(n \log n)$ steps with high
  probability (w.h.p., for short)\footnote{By the term ``with high probability'' (w.h.p., for
  short) we mean with probability $1 - 1/n^c$, for some constant $c >
  0$.} (c.f. Theorem~\ref{tree:main_result} of
  Section~\ref{sec:Tree}).
\end{itemize}
For a matching lower bound, we note that the cover time of a cobra
walk in a star graph is $\Omega(n \log n)$ w.h.p.  We
conjecture that the cover time for {\em any $n$-vertex graph}\/ is $O(n
\log n)$.  By exploiting the regular
structure of a grid, we establish improved and near-tight bounds for
the cover time on $d$-dimensional grids.
\begin{itemize}
\item
For a $d$-dimensional grid, we show that a cobra walk with $k \ge 2$
takes $\tilde{O}(n^{1/d})$ steps, w.h.p.  (cf. Theorem~\ref{the:grid} of 
Section~\ref{grid}).
\end{itemize}
We next show that the cover time of a cobra walk on the complete graph is logarithmic in $n$. Though this 
result may not particularly surprising, the method of proof is independently of
interest and serves as a ``warm-up'' and contrast to the proof of our result for expanders. 
%Instead of analyzing a cobra-walk on a graph, we map the cobra walk to 
%a simple random walk on a graph of exponential size (where active sets of a cobra 
%walk on $G$ map to vertices of the exponential graph). We then show that with overwhelmingly high probability,
%the walk advances towards vertices that corresponded to larger active sets, resulting in exponential growth of 
%the active set. 
\begin{itemize}
\item For $K_n$, the complete graph on $n$ vertices, w.h.p. a cobra walk covers $K_n$ in
$O(\log n)$ time. 
\end{itemize} 
Our main technical result is an analysis of cobra walks on expanders,
which are graphs in which every set $S$ of vertices of size at most half
the number of vertices has at least $\alpha |S|$ neighbors for a
constant $\alpha$, which is referred to as the expansion factor.
\begin{itemize}
\item
We show that for an $n$-vertex constant-degree expander, a cobra walk
covers a constant fraction of vertices in $O(\log n)$ steps and all the
vertices in $O(\log^2 n)$ steps w.h.p.
assuming that either the
branching factor or the expansion factor is sufficiently large
(cf. Theorems \ref{exp:phaseI} and \ref{exp:phaseII} of Section~\ref{sec:exp}).
\end{itemize}
Our analysis for expanders proceeds in two phases.  We show that in
the first phase, which consists of $O(\log n)$ steps, the branching
process dominates, resulting in an exponential growth in the number of
active verticess until a constant fraction of vertices become active, with
high probability.  In the second phase, though a large fraction of the
vertices continues to be active, dependencies caused by the coalescing
property prevent us from treating the process as multiple independent
random walks, analyzed in~\cite{AAKKLT} (or even $d$-wise independent
walks for a suitably large $d$).  
We overcome this hurdle by carefully
analyzing these dependencies and bounding relevant conditional
probabilities
% and define a time-inhomogeneous Markov process that is
%stochastically dominated by the cobra walk in terms of coverage.  We
%then use the notion of merging conductance and the machinery
%introduced in~\cite{mihail1989conductance} to analyze
%time-inhomogeneous Markov chains
 and establish an $O(\log n)$ bound
w.h.p. on the maximum hitting time, leading to an $O(\log^2 n)$ bound
on the cover time.

For establishing our results, it is often convenient to work with
branching factor $k = 2$.  Since the cover time for larger values of
the branching factor is at most the cover time for $k = 2$, all of our
results hold for $k \ge 2$.

\iffalse
 A main result of the paper is the cover time for graphs of suitably large expansion. Here we define a $\Delta$-regular graph $G$ to be an expander if every subset S of vertices of size $\leq \delta n$ has at least $\alpha |S|$ neighbors, where the neighborhood of $S$ can include members of $S$ as well. 

We show that for $\alpha$ sufficiently large and for $k \geq 1 + \ln (2\Delta / \alpha - 1)$, a cobra walk on expander $G$ with branching factor k will cover $\Omega(n)$ vertices of $G$ in $O(\log n)$ steps. We then show that a k-factor cobra walk on $G$ will cover the entire graph in $O(\log^2 n)$ steps. 
\fi

%By varying the branching factor
%and the time that a vertex remains infected, the process can also be
%viewed as a generalized rumor spreading model, with applications in
%both epidemiology and information dissemination.
\iffalse
We next compare  cobra walks and the implications of our results with other related randomized information spreading processes in networks.
We then discuss potential  scenarios where study of cobra walks can be useful.


We believe that our  results can also be generalized to understand
the time taken for an epidemic process in an SIS-type model to spread
in a network~\cite{GANESH,KES,PIET}.  By varying the branching factor
and the time that a vertex remains infected, the process can also be
viewed as a generalized rumor spreading model, with applications in
both epidemiology and information dissemination.

While the persistence time and
epidemic density of SIS-type epidemic models are well
studied~\cite{GANESH,KES}, here we analyze the time needed for a
SIS-type process to affect a constant fraction of the network.

In this paper, we study a new gossip model that we believe better
models several spreading phenomena.  Our model is best captured by the
following ``branching process'' on a finite graph $G$.  Let $S_t$
denote the set of active vertices in $G$, with $S_0$ being the initial
set of active vertices (usually this is a singleton set).  In round $t$,
each vertex in $S_{t-1}$ selects $k$ vertices uniformly at random (say,
with replacement) from its set of neighbors; $S_t$ is the union of all
the vertices selected in round $t$.  We focus on two questions: 

how long does it take for the information to reach a constant fraction
of the vertices?

how long does it take for the information to reach all the vertices?

It is instructive to consider the cases of $k = 1$ and $k = 2$.  The
case $k = 1$ is precisely a random walk in the graph, and we need not
discuss it further.  It is not hard to see that the case $k = 2$ will
eventually cover all the vertices; it is interesting to see how it
compares with the standard push process.  The standard push process
takes linear time to complete on the line graph.  The branching
process, however, will take $\Theta(n^2)$ to complete.

\fi



\iffalse
\subsection{Our results} 
We analyze the partial and full cover times of branching random walks
on bounded-degree regular expanders.  We say that a graph is an
$(\alpha,\delta)$-expander if the number of neighbors of every vertex 
set $S$ of vertices of size at most $\delta n$ is at least
$\alpha|S|$.  (Note that the neighbors of vertices in $S$ may include
vertices in $S$.)

\begin{itemize} 
\item We show that for any $\Delta$-regular $n$-vertex  $(\alpha,
  \delta)$-expander, the $k$-branching random walk covers at least
  $\delta n$ vertices in $O(\log n)$ steps for $k \ge 1 +
  \ln(2\Delta/(\alpha-1))$ assuming $\alpha$ is sufficiently large.
  In particular, for any random regular graph, the 2-branching random
  walk covers $\Omega(n)$ vertices in $O(\log n)$ steps with high
  probability.

\item We show that the cover time of a $k$-branching random walk on
  any bounded-degree regular $(\Omega(n), \alpha)$-expander graph is
  $O(\log^2 n)$ for $k \ge 1 + \ln(2\Delta/(\alpha-1))$, assuming
  $\alpha$ is sufficiently large.  In particular, the cover time of
  the 2-branching random walk on any random regular graph with
  constant degree is $O(\log^2 n)$.
\end{itemize}
\junk{We also extend the analysis of partial coverage to the SIS model.
\begin{itemize}
\item
If the ratio of the infection rate to the cure rate is sufficiently
high and the epidemic persists, then the epidemic reaches a constant
fraction of the vertices in $O(\log n)$ steps, with high probability.
\end{itemize}}

\fi


\subsection{Related work and comparison}

\noindent{\bf Branching and coalescing processes.} There is a large
body of work on branching processes (without coalescence) on various
discrete and non-discrete
structures~\cite{MR0163361,Madras1992255,benjamini2010trace}. A study
of coalescing random walks (without branching) was performed in
~\cite{cooper2012coalescing} with applications to voter models.
Others have looked at processes that incorporate branching and
coalescing particle
systems~\cite{arthreya2005branching,sun2008brownian}. However, these
studies treat the particle systems as continuous-time systems, with
branching, coalescing, and death rates on restricted-topology
structures such as integer lattices. To the best of our knowledge,
ours is the first work that studies random walks that branch and
coalesce in discrete time and on various classes of non-regular finite
graphs.
\smallskip

\noindent{\bf Random walks and parallel random walks.}
% Bounds in
%terms of spectral properties of graphs and tighter bounds for
%arbitrary graphs were obtained in~\cite{broder-karlin,chandra,feige}. 
Feige \cite{feige1,feige2} showed that the cover time of a random walk
on any undirected $n$-vertex connected graph is between $\Theta(n \log
n)$ and $\Theta(n^3)$ with both the lower and upper bounds being
achieved in certain graphs; in fact, the two bounds he established are
tight to within lower order terms.  With the rapidly increasing
interest in information (rumor) spreading processes in large-scale
networks and the gossiping paradigm (e.g., see \cite{sicomp} and the
references therein), there have been a number of studies on speeding
up the cover time of random walks on graphs.  One of the earliest
studies is due to Adler et al~\cite{AHKV03}, who studied a process on
the hypercube in which in each round a vertex is chosen uniformly at
random and covered; if the chosen vertex was already covered, then an
uncovered neighbor of the vertex is chosen uniformly at random and
covered.  For any $d$-regular graph, Dimitrov and Plaxton showed that
a similar process achieves a cover time of $O(n + (n \log
n)/d)$~\cite{DP05}.  For expander graphs, Berenbrink et al\ showed a
simple variant of the standard random walk that achieves a linear
(i.e., $O(n)$) cover time~\cite{berenbrink}.

It is instructive to compare cobra walks with other mechanisms to
speed up random walks as well as with gossip-based rumor spreading
mechanisms.  Perhaps the most related mechanism is that of parallel
random walks which was first studied in~\cite{broder} for the special
case where the starting vertices are drawn from the stationary
distribution, and in~\cite{AAKKLT} for arbitrary starting vertices.
Nearly-tight results on the speedup of cover time as a function of the
number of parallel walks have been obtained by~\cite{ElsasserS09} for
several graph classes including the cycle, $d$-dimensional meshes,
hypercube, and expanders.  (Also see~\cite{ER09} for results on mixing
time.)  Though cobra walks are similar to parallel random walks in the
sense that at any step multiple vertices may be selecting random
neighbors, there are significant differences between the two
mechanisms.  First the cover times of these walks are not comparable.
For instance, while $k$ parallel random walks may have a cover time of
$\Omega(n^2/\log k)$ for any $k \in [1,n]$~\cite{ElsasserS09}, a
$2$-branching cobra walk on a line has a cover time of $O(n)$.
Second, while the number of active vertices in $k$ parallel random walks
is always $k$, the number of active vertices in any $k$-branching cobra
walk is continually changing and {\em may not even be monotonic}.
Most importantly, the analysis of cover time of cobra walks needs to
address several dependencies in the process by which the set of active
vertices evolve; we use the machinery of Markov chains on graph tensor products
to obtain the cover time bound for bounded-degree expanders (see
Section~\ref{sec:exp}).

The works of \cite{DNP09-podc,DNPT10-podc} presented distributed
algorithms for performing a standard random walk in sublinear time,
i.e., in time sublinear in the length of the walk.
In particular, the algorithm of \cite{DNPT10-podc} performs a random walk
of length $\ell$ in $\tilde{O}(\sqrt{\ell D})$ rounds w.h.p. on an
undirected network, where $D$ is the diameter of the network.
The high-level idea behind this algorithm is to perform
several short walks in parallel and then stitch them carefully.   
However, this speed up comes with a drawback: the message complexity
of the above faster algorithm is much worse compared to the naive
sequential walk which takes only $\ell$ messages.  In contrast, we
note that the speedup in cover time given by a cobra walk over the
standard random walk comes only at the cost of a slightly worse
message complexity.

\smallskip
\noindent {\bf Gossip-based mechanisms.} 
Gossip-based information   propagation mechanisms have also been used
for information (rumor) spreading in distributed networks\footnote{Sometimes in the literature, ``gossiping" has been used
for {\em all-to-all} communication, and ``broadcasting" or ``rumor spreading" for {\em one-to-all} communication.}.
Gossip-based algorithms have also been successfully to {\em design} efficient
distributed algorithms for a variety of problems in networks such as
information dissemination, aggregate computation, constructing overlay
topologies (e.g., see \cite{sicomp} and the references therein).
%Such local algorithms are considered natural mathematical  models of how spreading
%occurs in real-world networks. 
In the most typical rumor spreading models, gossip involves either a
push step, in which vertices that are aware of a piece of information
 (being disseminated) pass it to random neighbors, or a pull step, in
 which vertices that are unaware of the information attempt to extract
 the information from one of their randomly chosen neighbors, or some
 combination of the two.  In such models, the knowledgeable vertices or
 the ignorant vertices participate in the dissemination problem in {\em
 every} round (step) of the algorithm. The main
 parameter of interest in many of these analyses is the number of
 rounds needed till all the vertices in the network get to know the
 information.
%It is known that in any graph, rumor spreading takes $O(n \log n)$ rounds.

The rumor spreading mechanism that is most closely related to cobra
walks is the basic push protocol, in which in every step every
informed vertex selects a random neighbor and pushes the information to
the neighbor, thus making it informed. (The push-pull version, unlike cobra, a vertex can choose a random neighbor and can get information.)  Feige et al. \cite{feige-rumor}
show that the push process completes in every undirected graph in
$O(n \log n)$ steps, with high probability. This paper also presented optimal
upper bounds of the push process in
various graph classes including random graphs, bounded
degree graphs, and the hypercube. Since then, the push
protocol and its variants (in particular, the push-pull protocol) have been extensively analyzed both for
special graphs, as well as for general graphs in terms of their
expansion properties (see e.g., \cite{panconesi1, panconesi2,
panconesi3, gia1, gia2, pana1, pana2}).  

 Though cobra walks and
push-based rumor spreading share the property that {\em multiple} vertices are
active in a given step (unlike the case in a standard random walk), the two mechanisms differ significantly.
While the set of active vertices in rumor spreading is monotonically
nondecreasing, this is not so in cobra walks, an aspect that makes the
analysis challenging especially with regard to full coverage. (Note that in a push process, once a node is active it remains active, unlike cobra.) However, we note that in any graph, the (expected) cover  time of the push process
is no worse that $k$ (where $k$ is the branching factor) times the cover time of the cobra walk process. This can be easily established by simulating one step of the  
of the cobra walk by $k$ (independent) steps of the push process. Thus, at least for constant $k$, the cover time of push is asymptotically no worse than that of  cobra walk. However, the message complexity of the push protocol can be
substantially different than that of cobra.  A simple example is the
star network, which the push protocol covers in $\Theta(n \log n)$
steps with a message complexity of $\Theta(n^2 \log n)$, while the
$2$-branching cobra walk has both cover time and message complexity
$\Theta(n \log n)$.  This can be extended to show similar results for
star-based networks that have been proposed as models for
Internet-scale networks~\cite{star-internet}. %For further work on gossip-based protocols, we refer to \cite{} and the references therein.

%\smallskip

\subsection{Applications}
\label{sec:apps}
As mentioned at the outset, cobra walks are closely related to the SIS
model in epidemics, but they may be easier to analyze using tools from
random walk and Markov chain analyses.   While the persistence time and
epidemic density of SIS-type epidemic models are well
studied~\cite{GANESH,KES,PIET}, to the best of our knowledge the time
needed for a SIS-type process to affect a large fraction (or the
whole) of the network has not been well-studied. The SIS model considered in these studies
is typically in a continuous time setting. For example, the work of \cite{GANESH} considers a model
where, at any time, infected vertices infect their neighbors with rate $\beta$ and vertices, once infected, recover at rate $\delta$ ($\delta$ is set to 1 without loss of generality).
It is important to note that this defines a Markov process where the absorbing state 0 can be reached from any starting state; thus an epidemic
always dies out. The main result of \cite{GANESH} is that if the ratio $\beta/\delta$ is less than $1/\lambda_{max}$, the largest eigenvalue
of the adjacency matrix of the underlying graph, then the epidemic dies out fast, i.e., in $O(\log n)$ time. On the other hand, if this ratio
is larger than the isoperimetric constant, then the epidemic will last for a long time, i.e., at least $\Omega(e^{n^{\alpha}})$.
A cobra walk can be considered as discrete time variant of the continuous SIS model with a difference. In a cobra walk, the epidemic does not die out, since there is at least one vertex that remains active in the network. Thus, while it is not interesting to study the time to extinction in a cobra walk,
it is relevant to study how long does it take to infect the whole or a fraction of the network; the amount of infected vertices in steady state (if it exists) is also worth studying. 
 Our results and
analyses of cobra walks can  be generalized to understand
the time taken for an epidemic process in an SIS-type model to spread
in a network.  
By varying the branching factor
and the time that a vertex remains infected, the process can also be
viewed as a generalized rumor spreading model, with applications in
both epidemiology and information dissemination.
%While the persistence time and epidemic
%density of SIS-type epidemic models are well studied, here we analyze
%the time needed for a SIS-type process to reach partial coverage of a
%graph.  

Cobra walks can also serve as a lightweight information dissemination
protocol in networks, similar to the push protocol. As pointed out
earlier, in certain types of networks, the message complexity incurred
by a cobra walk to cover a network can be smaller than that for the
push protocol.  This can be useful, especially in infrastructure-less
anonymous networks, where vertices don't have unique identities and and
may not even know the number of neighbors.  In such networks, it is
difficult to detect locally when coverage is completed\footnote{In
networks with identities and knowledge of neighbors, a vertex can
locally stop sending messages when all neighbors have the rumor. This
reduces the overall message complexity until cover time.}.  If vertices
have a good upper bound on $n$ (the network size), however, then vertices
can terminate the protocol after a number of steps equal to the
estimated cover time.  In such a scenario, message complexity is also
an important performance criterion.

\section{Preliminaries}
Let $G$ be a connected graph with vertex set $V$ and edge set $E$, and let $|V| = n$. We define a coalescing-branching (cobra) random walk on $G$ with branching factor $k$ starting at some arbitrary $v \in V$ as follows: At time $t = 0$ we place a pebble at $v$. Then in the next and every subsequent time step, every pebble in $G$ clones itself $k-1$ times (so that there are now $k$ indistinguishable pebbles at each vertex that originally had a pebble). Each pebble independently selects a neighbor of its current vertex uniformly at random and moves to it. Once all pebbles make their one-hop moves, if two or more pebbles are at the same vertex they coalesce into a single pebble, and the next round begins. In a cobra-walk, a vertex may receive a pebble an arbitrary number of times. 

For a time step $t$ of the process, let $S_t$ be the \textbf{active set}, the set of all vertices of $G$ that have a pebble. We will use two different definitions of the neighborhood of $S_t$: Let $N(S_t)$ be the \textbf{inclusive} neighborhood, the union of the set of neighbors of all vertices in $S_t$ (which can include members of $S_t$ itself). Let $\Gamma(S_t)$ be the \textbf{non-inclusive neighborhood}, which is the union of the set of neighbors of all vertices of $S_t$ such that $S_t \cap \Gamma(S_t) = \emptyset$.  

Let the expected {\bf maximum hitting time} $h_{max}$ of a cobra-walk on $G$ be defined as the $\max_{u,v \in V} \E[h_{u,v}]$ where $h_{u,v}$ is the time it takes for the first pebble arising from a cobra-walk starting at vertex $u$ to first reach $v$. 

We are interested in two different notions of cover time, which we define as the time until all vertices of $G$ have been visited by a cobra-walk at least once. Let $\tau_v$ be the minimum time $t$ such that, for a cobra-walk starting from $v$, $\forall u \in V - {v}$, $u \in S_t$ for some $t \leq \tau_v$ which may depend on $u$. Then we define the \textbf{cover time} of a cobra-walk on $G$ to be $\max_{v \in V} \tau_v$. We define the \textbf{expected cover time} to be $\max_{v \in V} \E[\tau_v]$. Note that in the literature for simple random walks, cover time usually refers to the expected cover times. 
In this paper we will show high-probability bounds on the  cover time.

In Section 6 we will be proving results for cobra-walks on
expanders. In this paper, we will use a spectral definition for
expanders and then use Tanner's theorem to translate that to
neighborhood and cut-based notions of expanders. 


\begin{definition}
\label{def:exp}
A \textbf{$d$-regular $\epsilon$-expander} is a $d$-regular graph
whose adjacency matrix has eigenvalues $\alpha_i$ such that
$|\alpha_i| \leq \epsilon d$ for $i \geq 2$, where $\epsilon \in (0,1)$.
\end{definition}

It is known that any $d$-regular $\epsilon$-expander $G$ with $n$
vertices approximates the complete graph $H = K_n$, with weight $d/n$
on each edge, in the following sense: for all $x \in \mathbb{R}^n$, $(1 -
\epsilon) x^T L_H x \le x^T L_G x \le (1 + \epsilon) x^T L_H
x$~\cite{spielman-notes}.  Tanner's theorem~\cite{tanner1984explicit}
then implies the following lower bound on neighborhood size in any
$d$-regular $\epsilon$-expander.

\begin{theorem}{~\cite{tanner1984explicit}}
\label{thm:tanner}
Let $G$ be a $d$-regular graph $\epsilon$-expander.  For all $S
\subseteq V$ with $|S| = \delta n$, we have $ |N(S)| \geq
\frac{|S|}{\epsilon^2 (1 - \delta) + \delta} \cdot$
\end{theorem}

In the analysis of random walks it is often important to qualify whether a graph is non-bipartite. In this analysis, all expander graphs are 
non-bipartite. This is implicit in the definition of the eigenvalues of $G$, which require $|\alpha_i| \leq \epsilon d < d$. 

%gopal --- I guess in the above it should be non-bipartite?

\junk{
We also want to define the notion of an $\epsilon$-approximation:
\begin{definition}
\label{def:epsapprox}
$G$ is an \textbf{$\epsilon$-approximation} for a graph $H$ if $(1-\epsilon) H \preccurlyeq G \preccurlyeq (1+\epsilon)H$, where $H \preccurlyeq G$ if for all $x$, $x^{T} L_H x \leq x^{T} L_G x$, where $L_G$ and $L_H$ are the Laplacians of G and H, respectively.
\end{definition} 

Finally, we will rely on the neighborhood expansion of a set $S$ on
$G$, where we define $N(S)$ as the inclusive neighborhood. For this we
will use Tanner's theorem~\cite{tanner1984explicit}, which gives us a
lower bound on the size of the neighborhood of $S$ for sufficiently
strong expanders.
}


\input{Tree} 

\input{grid} 

\input{Kn} 

\input{expanders} 

\section{Conclusion}

We studied a generalization of the random walk, namely the cobra walk,
and analyzed its cover time for trees, grids, complete graphs, and expander graphs.
The cobra walk is a natural random process, with potential
applications to epidemics and gossip-based information spreading.  We
plan to explore further the connections between cobra walks and the
SIS model, and pursue their practical implications.  From a
theoretical standpoint, there are several interesting open problems
regarding cobra walks that remain to be solved.  The  first one is to obtain a
tight bound for the cover time of cobra walks on expanders.  Our upper
bound is $O(\log^2 n)$, while the diameter $\Omega(\log n)$ is an easy
lower bound.  Another pressing open problem is to determine the
worst-case bound on the cover time of cobra walks on general graphs; we conjecture that it is
$O(n \log n)$ with high probability.
It will also be interesting to establish and compare the message
complexity of cobra walk with the standard random walk and other
gossip-based rumor spreading processes.


\section*{Acknowledgments}
We would like to thank the reviewers for their detailed and insightful
comments on earlier versions of this manuscript.  We are especially
grateful to the reviewer who urged us to revise the proof for the
second phase of the process on expanders, which has resulted in a
cleaner argument, and to the reviewer who suggested an improved result
and proof for the cover time of grids.

\newpage



\bibliographystyle{plain}
\bibliography{refs2,Distributed-RW2,expander,papers2,epidemics2}



\end{document}
